1. Field of the Invention
This invention relates to a reconfigurable circuit and a control method therefor. More particularly, this invention relates to a reconfigurable circuit having a plurality of processing elements that are reconfigured based on configuration information, and a control method for such a reconfigurable circuit.
2. Description of the Related Art
Conventionally, there is a reconfigurable circuit having a group of configurable operating units. The reconfigurable circuit forms a group of operating units based on configuration data so as to perform various kinds of processes. For a case where a single pipeline process cannot be implemented in such a reconfigurable circuit, there is proposed a method of implementing such a pipeline process by partitioning the reconfigurable circuit to correspond to pipeline stages and sequentially executing the operations of the stages (for example, see H. Schmit, “Incremental Reconfiguration for Pipelined Applications”, Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines (FCCM), P. 47 to 55, 1997).
FIG. 10 is a circuit block diagram of a conventional reconfigurable circuit.
As shown in this figure, the reconfigurable circuit has processing elements (PE: Processing Element) 101a to 101d and a network 102.
Each processing element 101a to 101d has a plurality of ALUs (Arithmetic Logical Unit), multipliers, and adders. The ALUs, Multipliers, and adders of the processing elements 101a to 101d are configured based on configuration data so that each executes an operation of a stage of a pipeline process.
The network 102 connects the processing elements 101a to 101d based on the configuration data so that the processing elements 101a to 101d can perform the pipeline process.
The pipeline process is a process of sequentially performing operations on sequentially inputted data. For example, multiply and accumulation represented by a FIR (Finite Impulse Response) filter are a pipeline process of sequentially performing multiply and accumulation operations on sequentially inputted data. An operation indicates a single operation out of operations to be sequentially performed. For example, speaking of the above-described multiply and accumulation, multiply and accumulation operations are sequentially performed on sequentially inputted data, and one of the multiply and accumulation operations is called a single operation. The pipeline process is divided into a plurality of stages and one or more operations are preformed at one stage.
FIG. 11 shows a pipeline process.
The illustrated pipeline process 111 is a single pipeline process comprising the operations OP1 to OP8. Arrows in this figure represent a data flow and it is assumed that data to be processed is sequentially inputted to the operation OP1. If the above-described multiply and accumulation are applied here for explanation, the operations OP1 to OP8 are the multiply and accumulation operations of eight stages to be performed on the data inputted to the operation OP1, where each operation OP1 to OP8 is a single multiply and accumulation operation.
Implementation of the pipeline process 111 in the reconfigurable circuit of FIG. 10 will be now described. As explained above, an operation of one stage of the pipeline process is assigned to each of the processing elements 101a to 101d of the reconfigurable circuit shown in FIG. 10. Since there are four processing elements 101a to 101d for the operations OP1 to OP8 of eight stages, the pipeline process is performed while assignment of the operations OP1 to OP8 to the processing elements 101a to 101d is changed every cycle.
FIG. 12 shows a flow of the pipeline process of FIG. 11 in the reconfigurable circuit of FIG. 10.
Illustrated squares represent the processing elements 101a to 101d of FIG. 10. The insides of the squares show the operations OP1 to OP8 assigned to the processing elements 101a to 101d. Note that data to be processed is sequentially inputted to the operation OP1 first.
In cycle 1, the operation OP1 is assigned to the processing element 101a and data is inputted. In cycle 2, the operation OP2 is assigned to the processing element 101b. At this time, data resulted from the operation OP1 in cycle 1 is inputted to the processing element 101b and next data is inputted to the operation OP1. Then the operations OP3 and OP4 are sequentially assigned to the processing elements 101c and 101d in cycles 3 and 4, respectively, and data resulted from the operations OP2 and OP3 of the preceding stages (previous cycles) is inputted thereto. In addition, data is sequentially inputted to the operation OP1.
In cycle 5, since there is no other processing elements for assignment of the operation OP5, the operation OP5 is assigned to the processing element 101a. At this time, it is designed that data from the processing element 101d (resulted from the operation OP4) is outputted to the processing element 101a (operation OP5).
In cycles 6 to 8, the operations OP6 to OP8 are sequentially assigned to the processing elements 101b to 101d, respectively, and data resulted from the operations OP5 to OP7 of the preceding stages (previous cycles) is inputted thereto. It should be noted that new data is not inputted in cycles 5 to 8. This is because the operations OP1 to OP4 are not assigned to the processing elements 101a to 101d and so the pipeline process cannot be performed. Although unillustrated, in cycle 9, the operation OP1 is assigned to the processing element 101a and next data is inputted.
The above-described method of implementing a pipeline process in the processing elements 101a to 101d by sequentially switching the stages of the pipeline process requires a shorter processing time as compared with a method of implementing implementable pipeline stages in the processing elements 101a to 101d at one time. This is because, according to the method of implementation at one time, when the operations of the implemented pipeline stages are completed, the operation results should be temporarily saved in a memory unit and then subsequent pipeline stages should be implemented in the processing elements 101a to 101d. By contrast, according to the method of implementation by sequentially switching the stages of the pipeline process, operation results may not be temporarily saved into a memory unit, resulting in shortening a processing time.
A case where a plurality of operations should be simultaneously performed at a stage of a pipeline process will be now described. In this case, a plurality of pipeline stages should be simultaneously assigned to processing elements.
FIG. 13 shows a pipeline process in a case of simultaneously assigning a plurality of pipeline stages to processing elements.
In the illustrated pipeline process 112, the operations OP1 and OP2 are executed at the first stage. The operations OP3 and OP4 are executed at the second stage. Then, the operations OP5 to OP7 are sequentially executed at respective stages. Arrows in this figure represent a data flow and it is assumed that data to be processed is sequentially inputted to the operations OP1 and OP2. Implementation of this pipeline process 112 in the reconfigurable circuit of FIG. 10 will be now described.
FIG. 14 shows a flow of the pipeline process of FIG. 13 in the reconfigurable circuit of FIG. 10.
Illustrated squares represent the processing elements 101a to 101d of FIG. 10. The insides of the squares show the operations OP1 to OP7 assigned to the processing elements 101a to 101d. Data to be processed is sequentially inputted to the operations OP1 and OP2 first. None indicates a status where no operation is assigned.
At the first stage of the pipeline 112 shown in FIG. 13, the two operations OP1 and OP2 should be executed. In addition, at the second stage of the pipeline process 112, the two operations OP3 and OP4 should be executed. Therefore, the reconfigurable circuit shown in FIG. 10 should be configured so that a combination of the processing elements 101a and 101b and a combination of the processing elements 101c and 101d each can simultaneously execute the two operations, as shown in FIG. 14.
In cycle 1, the operations OP1 and OP2 are assigned to the processing elements 101a and 101b and data is inputted to them. In cycle 2, the operations OP3 and OP4 are assigned to the processing elements 101c and 101d. At this time, data resulted from the operations OP1 and OP2 in cycle 1 is inputted to the processing elements 101c and 101d. On the other hand, next data is inputted to the operations OP1 and OP2. In cycles 3 to 5, the operations OP5 to OP7 are sequentially assigned to the combination of the processing elements 101a and 101b or the processing elements 101c and 101d, and data from the preceding stages is inputted thereto.
The operations OP5 to OP7 should be executed each at one stage as shown in FIG. 13. Therefore, only one operation is implemented in each of a combination of the processing elements 101a and 101b and a combination of the processing elements 101c and 101d. As described above, this is because each of the combinations of the processing elements 101a and 101b and the processing elements 101c and 101d are configured so as to simultaneously execute two operations. Therefore, out of the processing elements 101a and 101b and the processing elements 101c and 101d, one processing element becomes free (none state), which deteriorates efficiency of implementation.
In cycle 6, following cycle 5, the operation OP7 should be assigned to the processing element 101a, 101b. This is because data inputted in cycle 1 is processed by the operation OP7 in cycle 5, but data inputted in cycle 2 has been processed by the operations up to the operation OP6 by the time of cycle 5 and the data should be processed by the operation OP7 in cycle 6. No data is inputted in cycles 3 to 6 and next data can be inputted in next cycle 7.
FIG. 15 is a timing chart of input/output of data in the pipeline process of FIG. 13.
CLK of this figure indicates timing of executing operations. IN indicates input timing of data to the operations OP1 and OP2. OUT indicates output timing of data from the operation OP7.
As shown in this figure, data is inputted to the operations OP1 and OP2 at CLKs 1 and 2 (CLK corresponds to cycle shown in FIG. 14). Data inputted at CLK 1 is processed in the operation OP7 at CLK 5 as explained with reference to FIG. 14. Then, the data inputted at CLK 1 is outputted at CLK 6 as shown in FIG. 15. Data inputted at CLK 2 is processed in the operation OP7 at CLK 6 as explained with reference to FIG. 14. Then, the data inputted at CLK 2 is outputted at CLK 7 as shown in FIG. 15. The operations OP1 and OP2 are assigned to the processing elements 101a and 101b at CLK 7 again and next data is inputted thereto.
In a case where a plurality of operations are to be executed simultaneously at a stage of a pipeline process, the plurality of operations should be assigned to processing elements at the same time. This case produces a problem in that efficiency of implementation of the pipeline process in the processing elements deteriorates and processing performance degrades.